
// 网格形 
class Node
{
    NodeType nodeType;
    Node Parent;
    int G; (Patent.G + distance(this.pos,parent.pos))
    int H; (distance(this.pos,end.pos));
    int F=>G+H;

    int x;
    int y;
    Vector2 pos = new Vector2();
    enum NodeType{
        walk,
        stop,

    }

    public Node(Vector2 pos,NodeType nodeType,int x ;int y)
    {
        this.pos = pos;
        this.nodeType = nodeType;
        this.x = x;
        this.y = y;
          
    }
}

class Graph
{
    List<List<Node>>m_Graph;
    List<Node>Open  = new List<Node>;
    List<Node>Closed = new List<Node>;
    List<Node>Path = new List<Node>;

    private int mapW;
    private int mapH;

    int xOffest = 2;
    int yOffest = 2;

    Node start;
    Node end;

    Node curNode;

    public void InitMap(int w,int h)
    {
        m_Graph = new List<List<node>>();
        mapW = w;
        mapH = h;


        for(int i=0;i<w;i++)
        {
            for(int j=0;j<h;j++)
            {
                m_Graph[i,j] = new(new Vector2(i + i* xOffest, j + j*xOffest),NodeType.Walk,i,j);
                if(Random(0.10)<2)
                {
                    m_Graph[i,j].nodeType = NodeType.Stop;
                }
            }
        }

        open.Clear();
        closed.Clear();

    }


    List<Node> TraveserEnter(Node node)
    {
        List<Node>res = new List<Node>();
        if(IsIndexInMap(m))

        return res; //拿到的是计算好F的List

    }


    public void Find(Vector2 start;Vector2 endPos)
    {
        if(IsMapExternal(start))
        {
            Log.logger($"{start} 越界");
            retrun;
        }
            
        if(IsMapExternal(endPos))
        {
            Log.logger($"{endPos} 越界");
            retrun;
        }


        var nodeStart = this.m_Graph.Find(v=>v.pos == start);
        var nodeEnd = this.m_Graph.Find(v=>v.pos == endPos);

        if(nodeStart.nodeType == NodeType.stop)
        {
            Log.logger($"{start} 是不可行走点");
            return;
        }

        if(nodeEnd.nodeType == NodeType.stop)
        {
            Log.logger($"{endPos} 是不可行走点");
            return;
        }
        FindEndPoint(nodeStart);

    }


    void FindEndPoint(Node node)
    {

        //正式开始A*
        for(int i = -1;i<2;i++)
        {
            for(int j =-1;j<2;j++)
            {
                if(i==0 && j==0)
                    continue;

                if(node == nodeEnd)return ;    
                if(IsMapExternal(i +i*xOffestj ,j *yOffest))
                    continue;
                var curnode = m_Graph[nodeStart.x+i,nodeStart.y+j];
                if(curnode.nodeType == NodeType.Stop)
                    continue;
                
                //这还要过滤 如果该点不在open 和 closed中
                if(Open.Find(v=>v == curnode)!=null)
                    continue;
                if(Closed.Find(v=>v == curnode)!=null)
                    continue; 


                curnode.Parent = nodeStart;
                float d = 1f;
                if(i!=0 || && j!=0)
                {
                    d = 1.4;
                }

                curnode.G = parent.G +d;
                curnode.H = Math.abs(curnode.x -endPos.x) +Math.abs(curnode.y -endPos.y);
                Open.Add(curnode);



            }
        }

        if(Open.count==0)
        {
            return ;
        }
        Open.Sort((node1,node2)=>{
            return node1.F <node2.F ? -1:1;
        });

        float min =9999;

        List<int>RemoveIndex;
        for(int i<0;i<Open.Length;i++)
        {
            if(Open.F <=min)
            {
                Closed.Add(Open[i]);
                FindEndPoint(Open[i]);
            }
            else 
                break;
        }

        for(int i<0;i<RemoveIndex.Length;i++)
        {
            Open.Removeat(RemoveIndex[i]);
        }


    }
    private bool IsIndexInMap(float x ,float y)
    {
        if(x<0 || x>=w) return true;
        if(y<0  || y>=h) return true;
        return false;
    }
    private bool IsMapExternal(loat x ,float y)
    {
        if(x<0 || x>=w) return true;
        if(y<0  || y>=h) return true;
        return false;
    }


}